
"""
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
"""
import sys
from collections import Counter
from typing import List


class Solution:

    def findAnagrams(self, s: str, p: str) -> List[int]:
        left = 0
        right = 0
        need = Counter(p)
        window = Counter()
        valid = 0
        res = []

        while right < len(s):
            # 扩大窗口
            c = s[right]
            right += 1
            if c in need:
                window[c] += 1
                if need[c] == window[c]:
                    valid += 1

            while right - left >= len(p):
                # 更新结果
                if valid == len(need):
                    res.append(left)
                # 减小窗口
                c = s[left]
                left += 1
                if c in need:
                    if need[c] == window[c]:
                        valid -= 1
                    window[c] -= 1

        return res